/**
 * 
 */
package com.gragra.sampling.binary;
import java.util.Arrays;
import com.gragra.benchmark.FractionAblePopulationStructure;
import com.gragra.sampling.PopulationProbabilityAssigner;
import com.gragra.sampling.PopulationSamplingStructure;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.sequentialStructure.WordAndTagHolder;
import com.gragra.util.StringToInt;
/**
 * @author Christoph Teichmann
 * 14.09.2013
 */
public abstract class BinaryStructure extends WordAndTagHolder implements
		PopulationSamplingStructure, ThreadedToString, FractionAblePopulationStructure, HeadAssignmentStructure
{
	/**
	 * @return the sampleHead
	 */
	protected boolean samplesHead()
	{return this.sampleHead;}
	/* (non-Javadoc)
	 * @see com.gragra.benchmark.FractionAblePopulationStructure#getNumberSeen(java.lang.String)
	 */
	@Override
	public double getNumberSeen(String goldTwo)
	{return this.cs.getNumberSeen(goldTwo);}
	/**
	 * 
	 */
	private final boolean sampleHead;
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#resample(com.gragra.sampling.PopulationProbabilityAssigner, double, int, com.gragra.sampling.ThreadedUniformAccess)
	 */
	@Override
	public void resample(PopulationProbabilityAssigner pa, double annealing,
			int thread, ThreadedUniformAccess tua)
	{
		if(decideSkipable())
		{return;}
		this.removeBefore(pa,thread);
		coreSampling(annealing, thread, tua, pa);
		if(this.sampleHead)
		{
			for(int splitPoint=1;splitPoint<this.getLength();++splitPoint)
			{this.sampleHead(splitPoint,pa,annealing,thread,tua);}
		}
		this.addAfter(pa,thread);
	}
	/**
	 * 
	 * @param splitPoint
	 * @param ba
	 * @param annealing
	 * @param thread
	 * @param tua
	 */
	private void sampleHead(int splitPoint, PopulationProbabilityAssigner ba,
			double annealing, int thread, ThreadedUniformAccess tua)
	{
		this.setHeadDirection(splitPoint, true, thread);
		double probLeft = ba.makeLogProb(this, thread)*annealing;
		this.setHeadDirection(splitPoint, false, thread);
		double probRight = ba.makeLogProb(this, thread);
		double max = Math.max(probLeft, probRight);
		double sum = probLeft = Math.exp(probLeft-max);
		sum += Math.exp(probRight-max);
		if(tua.nextDouble(thread) < probLeft/sum)
		{this.setHeadDirection(splitPoint, true, thread);}
	}
	/**
	 * @return
	 */
	protected boolean decideSkipable()
	{return this.getLength() < 2;}
	/**
	 * 
	 * @param ba
	 * @param thread
	 */
	protected void addAfter(PopulationProbabilityAssigner ba, int thread)
	{}
	/**
	 * 
	 * @param ba
	 * @param thread
	 */
	protected void removeBefore(PopulationProbabilityAssigner ba, int thread)
	{}
	/**
	 * 
	 * @param annealing
	 * @param thread
	 * @param tua
	 * @param ba
	 */
	protected abstract void coreSampling(double annealing, int thread,
			ThreadedUniformAccess tua, PopulationProbabilityAssigner ba);
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		for(int thread=0;thread<this.getNumberOfThreads();++thread)
		{
			if(thread!=0)
			{sb.append("\r\n");}
			sb.append(this.toString(thread));
		}
		return sb.toString();
	}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#getBest(com.gragra.sampling.PopulationProbabilityAssigner)
	 */
	@Override
	public String getBest(PopulationProbabilityAssigner pa)
	{return this.cs.getBest(this,pa);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#minRisk(com.gragra.sampling.PopulationProbabilityAssigner)
	 */
	@Override
	public String minRisk(PopulationProbabilityAssigner pa)
	{return this.cs.minRisk(this,pa);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#addSample()
	 */
	@Override
	public void addSample()
	{this.cs.addSample(this);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#setBest(int)
	 */
	@Override
	public void setBest(int thread)
	{cs.setBest(this,thread);}
	/**
	 * 
	 */
	private final ConvertSample cs;
	/**
	 * 
	 * @return
	 */
	public int getNumberOfThreads()
	{return this.dominated.length;}
	/**
	 * 
	 * @param splitPosition
	 * @param thread
	 * @return
	 */
	public int getNodeSplittingAt(int splitPosition,int thread)
	{return this.middleNode[thread][splitPosition];}
	/**
	 * 
	 */
	private final int[][] middleNode;
	/**
	 * 
	 * @param node
	 * @param thread
	 * @return
	 */
	public int getMiddle(int node, int thread)
	{return this.getTo(this.getDominated(node, true, thread), thread);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.binary.ThreadedToString#toString(int)
	 */
	@Override
	public String toString(int thread)
	{return this.toString(thread,this.getRootPosition());}
	/**
	 * 
	 * @param thread
	 * @param rootPosition
	 */
	private String toString(int thread, int node)
	{
		if(node < this.getLength())
		{return "("+StringToInt.reverse(this.getTag(node))+" "+StringToInt.reverse(this.getWord(node))+")";}
		StringBuilder sb = new StringBuilder();
		sb.append("( ");
		sb.append(this.toString(thread,this.getDominated(node, true, thread)));
		if(this.getHeadLeft(this.getMiddle(node, thread), thread) && this.samplesHead())
		{sb.append("<-");}
		sb.append(" ");
		sb.append(this.toString(thread,this.getDominated(node, false, thread)));
		if(!this.getHeadLeft(this.getMiddle(node, thread), thread) && this.samplesHead())
		{sb.append("<-");}
		sb.append(" )");
		return sb.toString();
	}
	/**
	 * 
	 * @return
	 */
	public int getRootPosition()
	{return dominated[0].length-1;}
	/**
	 * 
	 */
	private final int[][] from;
	/**
	 * 
	 * @param thread
	 * @param node
	 * @return
	 */
	public int getFrom(int node, int thread)
	{return this.from[thread][node];}
	/**
	 * 
	 */
	private final int[][] to;
	/**
	 * 
	 * @param thread
	 * @return
	 */
	public int getTo(int node, int thread)
	{return this.to[thread][node];}
	/**
	 * 
	 */
	private final int[][][] dominated;
	/**
	 * 
	 */
	private final int[][] above;
	/**
	 * 
	 * @param thread
	 * @return
	 */
	public int getAbove(int node, int thread)
	{return this.above[thread][node];}
	/**
	 * 
	 * @param thread
	 * @return
	 */
	public int getDominated(int node, boolean left, int thread)
	{return this.dominated[thread][node][left ? 0 : 1];}
	/**
	 * @param threads
	 */
	protected void initArrs(int threads)
	{
		for(int thread=0;thread<threads;++thread)
		{
			int[][] dom = this.dominated[thread];
			int[] from = this.from[thread];
			int[] to = this.to[thread];
			for(int i=0;i<this.getLength();++i)
			{
				dom[i][0] = dom[i][1] = i;
				from[i] = i;
				to[i] = i+1;
			}
		}
	}
	/**
	 * @param wth
	 */
	public BinaryStructure(WordAndTagHolder wth, int threads, ConvertSample cs, boolean sampleHead)
	{
		super(wth);
		int size = (this.getLength()*2)-1;
		dominated = new int[threads][size][2];
		above = new int[threads][size];
		from = new int[threads][size];
		to = new int[threads][size];
		this.middleNode = new int[threads][this.getLength()];
		this.cs = cs;
		initArrs(threads);
		this.headLeft = new boolean[threads][this.getLength()];
		this.head = new int[threads][this.getLength()];
		this.headsReady = new boolean[threads];
		Arrays.fill(this.headsReady, false);
		this.sampleHead = sampleHead;
		this.splitHead = new int[threads][this.getLength()];
	}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#initialize(com.gragra.sampling.PopulationProbabilityAssigner, com.gragra.sampling.ThreadedUniformAccess)
	 */
	@Override
	public void initialize(PopulationProbabilityAssigner pa,
			ThreadedUniformAccess tua)
	{
		if(this.getLength() == 1)
		{initializeSingle();}
		for(int thread=0;thread<this.getThreadNumber();++thread)
		{initialize(pa,tua,thread);}
	}
	/**
	 * 
	 */
	private void initializeSingle()
	{
		for(int thread=0;thread<this.getThreadNumber();++thread)
		{this.above[thread][0] = 0;}
	}
	/**
	 * 
	 * @param pa
	 * @param tua
	 * @param thread
	 */
	private void initialize(PopulationProbabilityAssigner pa,
			ThreadedUniformAccess tua, int thread)
	{
		if(this.samplesHead())
		{
			for(int i=0;i<this.headLeft[thread].length;++i)
			{this.headLeft[thread][i] = tua.nextBoolean(thread);}
		}
		makeLeftRightAround(thread%this.getLength(),thread,tua);
	}
	/**
	 * 
	 * @param i
	 * @param thread
	 */
	private void makeLeftRightAround(int pos, int thread, ThreadedUniformAccess tua)
	{
		boolean dir = tua.nextBoolean(0);
		int unused = this.getLength();
		int lastUsed = pos;
		if(dir)
		{leftToRight(pos, thread, unused, lastUsed);}
		else
		{rightToLeft(pos, thread, unused, lastUsed);}
	}
	/**
	 * @param pos
	 * @param thread
	 * @param unused
	 * @param lastUsed
	 */
	private void rightToLeft(int pos, int thread, int unused, int lastUsed)
	{
		for(int k=pos+1;k<this.getLength();++k)
		{
			int left = lastUsed;
			int right = k;
			int top = unused;
			this.subsume(left, right, top, thread);
			lastUsed = unused;
			++unused;
		}
		for(int i=pos-1;i>=0;--i)
		{
			int left = i;
			int right = lastUsed;
			int top = unused;
			this.subsume(left, right, top, thread);
			lastUsed = unused;
			++unused;
		}
	}
	/**
	 * @param pos
	 * @param thread
	 * @param unused
	 * @param lastUsed
	 */
	private void leftToRight(int pos, int thread, int unused, int lastUsed)
	{
		for(int i=pos-1;i>=0;--i)
		{
			int left = i;
			int right = lastUsed;
			int top = unused;
			this.subsume(left, right, top, thread);
			lastUsed = unused;
			++unused;
		}
		for(int k=pos+1;k<this.getLength();++k)
		{
			int left = lastUsed;
			int right = k;
			int top = unused;
			this.subsume(left, right, top, thread);
			lastUsed = unused;
			++unused;
		}
	}
	/**
	 * @param thread
	 * @param left
	 * @param right
	 * @param top
	 */
	public final void subsume(int left, int right, int top, int thread)
	{
		this.headsReady[thread] = false;
		this.above[thread][right] = top;
		this.above[thread][left] = top;
		this.dominated[thread][top][0] = left;
		this.dominated[thread][top][1] = right;
		this.from[thread][top] = this.from[thread][left];
		this.to[thread][top] = this.to[thread][right];
		int mid = this.getTo(left, thread);
		this.middleNode[thread][mid] = top;
	}
	/**
	 * 
	 * @return
	 */
	private int getThreadNumber()
	{return this.dominated.length;}
	/**
	 * extracts elements from the left daughter and shifts them to the right
	 * @param node
	 * @param thread
	 */
	public void flipRight(int node,int thread)
	{
		if(node < this.getLength())
		{return;}
		int left = this.getDominated(node, true, thread);
		if(left < this.getLength())
		{return;}
		int right = this.getDominated(node, false, thread);
		int leftLeft = this.getDominated(left, true, thread);
		int leftRight = this.getDominated(left, false, thread);
		this.subsume(leftRight, right, left, thread);
		this.subsume(leftLeft, left, node, thread);
	}
	/**
	 * extracts elements from the right daughter and shifts them to the left
	 * @param node
	 * @param thread
	 */
	public void flipLeft(int node,int thread)
	{
		if(node < this.getLength())
		{return;}
		int right = this.getDominated(node, false, thread);
		if(right < this.getLength())
		{return;}
		int left = this.getDominated(node, true, thread);
		int rightLeft = this.getDominated(right, true, thread);
		int rightRight = this.getDominated(right, false, thread);
		this.subsume(left, rightLeft, right, thread);
		this.subsume(right, rightRight, node, thread);
	}
	/**
	 * 
	 */
	private final boolean[][] headLeft;
	/**
	 * 
	 * @param forSplit
	 * @param thread
	 * @return
	 */
	protected boolean getHeadLeft(int forSplit, int thread)
	{return this.headLeft[thread][forSplit];}
	/**
	 * 
	 * @param forSplit
	 * @param toLeft
	 * @param thread
	 */
	public final void setHeadDirection(int forSplit, boolean toLeft, int thread)
	{
		this.headsReady[thread] = false;
		this.headLeft[thread][forSplit] = toLeft;
	}
	/**
	 * 
	 */
	private final int[][] head;
	/**
	 * 
	 */
	private final boolean headsReady[];
	/**
	 * 
	 * @param forWord
	 * @param thread
	 * @return
	 */
	public final int getHeadPosition(int forWord, int thread)
	{
		if(!this.headsReady[thread])
		{
			int root = makeHeads(this.getRootPosition(), thread);
			this.head[thread][root] = this.getLength();
			this.headsReady[thread] = true;
		}
		return this.head[thread][forWord];
	}
	/**
	 * 
	 * @param thread
	 */
	private int makeHeads(int node, int thread)
	{
		if(node < this.getLength())
		{return node;}
		int left = this.makeHeads(this.getDominated(node, true, thread), thread);
		int right = this.makeHeads(this.getDominated(node, false, thread), thread);
		if(this.headLeft[thread][this.getMiddle(node, thread)])
		{
			this.head[thread][right] = left;
			this.splitHead[thread][this.getMiddle(node, thread)] = left;
			return left;
		}
		else
		{
			this.head[thread][left] = right;
			this.splitHead[thread][this.getMiddle(node, thread)] = right;
			return right;
		}
	}
	/**
	 * 
	 * @return
	 */
	public int getDependencyRootPosition()
	{return this.getLength();}
	/**
	 * 
	 */
	private final int[][] splitHead;
	/**
	 * 
	 * @param node
	 * @param thread
	 * @return
	 */
	public int getNodeHeadPosition(int node, int thread)
	{return this.splitHead[thread][this.getMiddle(node, thread)];}
}